//
//  Problem1727.swift
//  TestProject
//
//  Created by 武侠 on 2021/6/3.
//  Copyright © 2021 zhulong. All rights reserved.
//

import UIKit

/*
 1727. 重新排列后的最大子矩阵
 给你一个二进制矩阵 matrix ，它的大小为 m x n ，你可以将 matrix 中的 列 按任意顺序重新排列。
 请你返回最优方案下将 matrix 重新排列后，全是 1 的子矩阵面积。

 示例 1：
     输入：matrix = [[0,0,1],[1,1,1],[1,0,1]]
     输出：4
     解释：你可以按照上图方式重新排列矩阵的每一列。
     最大的全 1 子矩阵是上图中加粗的部分，面积为 4 。
 示例 2：
     输入：matrix = [[1,0,1,0,1]]
     输出：3
     解释：你可以按照上图方式重新排列矩阵的每一列。
     最大的全 1 子矩阵是上图中加粗的部分，面积为 3 。
 示例 3：
     输入：matrix = [[1,1,0],[1,0,1]]
     输出：2
     解释：由于你只能整列整列重新排布，所以没有比面积为 2 更大的全 1 子矩形。
 示例 4：
     输入：matrix = [[0,0],[0,0]]
     输出：0
     解释：由于矩阵中没有 1 ，没有任何全 1 的子矩阵，所以面积为 0 。
 提示：
     m == matrix.length
     n == matrix[i].length
     1 <= m * n <= 10^5
     matrix[i][j] 要么是 0 ，要么是 1 。
 */
@objcMembers class Problem1727: NSObject {
    func solution() {
        print(largestSubmatrixL([[0,0,1],[1,1,1],[1,0,1]]))
        print(largestSubmatrixL([[1,0,1,0,1]]))
        print(largestSubmatrixL([[1,1,0],[1,0,1]]))
        print(largestSubmatrixL([[0,0],[0,0]]))
//        print(largestSubmatrix([[1,1,1],[1,1,1],[1,0,1],[1,1,0],[0,0,1],[1,1,1],[0,1,1],[1,0,1],[0,0,1],[1,1,1],[1,0,1],[1,1,0],[1,1,0],[1,1,1],[1,0,1],[1,1,1],[1,0,1],[1,1,1],[0,1,0],[1,1,0]]))
    }
    
    /*
     超时
     比如(0,0)，让这个点变成1，我们看看以这个点的左上角能有多少个1，那么我们让数组重写排序，规则就是：
     让第一排的1集中到左侧，然后按照列的1的个数排序
     */
    func largestSubmatrix(_ matrix: [[Int]]) -> Int {
        var maxValue = 0
        for i in 0..<matrix.count {
            var list:[Int] = Array(repeating: 0, count: matrix[0].count)
            for j in 0..<matrix[0].count {
                for k in i..<matrix.count {
                    if matrix[k][j] == 0 {
                        break
                    }
                    list[j] += 1
                }
            }
            list.sort()
            print(list)
            var chang = Int.max
            for (i, n) in list.enumerated().reversed() {
                if n == 0 {
                    break
                }
                chang = min(chang, n)
                maxValue = max(maxValue, chang * (list.count-i))
                print(i, n, chang, maxValue)
            }
        }
        return maxValue
    }
    
    /*
     原来的思想是：遍历每一层，统计这一层每列连续1的个数，使用了3个for
     改变思路，变成数组，使用类似前缀和的方式，事先统计所有的连续1的个数
     */
    func largestSubmatrixL(_ matrix: [[Int]]) -> Int {
        // 统计连续1的个数
        var list:[[Int]] = Array(repeating: Array(repeating: 0, count: matrix[0].count), count: matrix.count)
        for l in 0..<matrix[0].count {
            list[0][l] = matrix[0][l]
            for r in 1..<matrix.count {
                list[r][l] = matrix[r][l] == 1 ? list[r-1][l] + 1 : 0
            }
        }
        
        var maxValue = 0
        for i in (0..<list.count).reversed() {
            list[i].sort()
            for (i, n) in list[i].reversed().enumerated() {
                maxValue = max(maxValue, n * (i+1))
            }
        }
        
        return maxValue
    }
}

/*
 [0,0,1],
 [1,1,1],
 [1,0,1]
 
 [0, 0, 1],
 [1, 1, 2],
 [2, 0, 3]
 */
